Deduplication storage systems, such as EMC Data Domain storage systems, perform deduplication to minimize the amount of storage consumed. Instead of storing two copies of the same piece of data, a single copy is stored (e.g., with two links or identifiers referencing the single copy). Companies are storing and managing ever growing amounts of data (sometimes referred to as “big data”) which may require thousands or tens of thousands of deduplication nodes in a distributed deduplication storage system. Typically, the number of deduplication nodes in a distributed deduplication storage system fluctuates over time. For example, the number of deduplication nodes may decrease (e.g., because one or more deduplication nodes fail) or increase (e.g., because new deduplication node(s) is/are brought online). When this happens, some deduplication storage systems redistribute a significant amount of data in the system which consumes resources (e.g., I/O resources between deduplication nodes) and impedes other requests or services (e.g., a service request from a user). It would be desirable if distributed deduplication storage systems were better able to handle fluctuating numbers of deduplication nodes.